/*
随机选择算法，时间复杂度O(n) , 空间O(1)
 */

public class RandomizedSelect {
    public static void main(String[] args) {
        int[] arr = {7,9,4,3,2,6,1,8,5};
        int num = findKthLargest(arr,9);
        System.out.println(num);
    }

    //找到乱序数组中第K大的数
    public static int findKthLargest(int[] arr, int K) {
        //数组长度为10
        //找到第1大的数相当于排序后数组中最后一个的数 下标为arr.length-1;
        //找到第10大的数相当于排序后数组中第一个数，下标为arr.length-10;
        return randomizedSelect(arr, arr.length-K);
    }

    public static int randomizedSelect(int[] arr, int i) {
        int ans = -1;
        int l = 0;
        int r = arr.length-1;
        while(l <= r) {
            int key = arr[l+(int)Math.random()*(r-l+1)];
            int[] range = partition(arr,l,r,key);
            int left = range[0];
            int right= range[1];
            if(i<left) {
                r = left-1;
            }else if(i>right) {
                l = right + 1;
            }else {
                ans = arr[i];
                break;
            }
        }
        return ans;
    }

    public static int[] partition(int[] arr,int l, int r, int x) {
        int[] range = new int[2];
        int a = l;
        int b = r;
        int i = l;
        while ( i <= b ) {
            if(arr[i] < x) {
                swap(arr,a,i);
                a++;
                i++;
            }
            else if( arr[i] > x){
                swap(arr,b,i);
                b--;
            }else {
                i++;
            }
        }
        range[0] = a;
        range[1] = b;
        return  range;
    }

    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }



}
